package com.adee.algorithm.learn;


import com.adee.algorithm.utils.Util;

import java.util.Arrays;

public class Test001_binarySearch {
    public static void main(String[] args) {
        test_binarySearch4();
    }

    /**
     * 数组中有重复元素，查找和目标值相等的首个值的位置
     * 实现：在普通二分查找的基础上，找到目标值后，向前遍历比较每个元素值
     * 缺点：当数组中出现大量重复数时，时间复杂度退化为n
     */
    public static int binarySearch(int[] arr, int a) {
        if (arr == null) return -1;
        int low = 0, high = arr.length-1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a == arr[mid]) {
                int p = mid;
                while(p >= low && arr[p] == a) --p;
                return ++p;
            } else if (a < arr[mid]) {
                high = mid-1;
            } else {
                low = mid+1;
            }
        }
        return -1;
    }

    /**
     * 数组中有重复元素，查找和目标值相等的首个值的位置
     * 上面 binarySearch 方法的优化
     * 优化逻辑：普通二分查找法中，当找到目标值后，继续二分查找前面部分
     */
    public static int binarySearch2(int[] arr, int a) {
        if (arr == null || arr.length == 0) return -1;
        int low = 0, high = arr.length-1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (a <= arr[mid]) {
                high = mid;
            } else {
                low = mid;
            }
            if(high - low == 1) {
                if(arr[low] == a) return low;
                if(arr[high] == a) return high;
                return -1;
            }
        }
        return -1;
    }

    // arr已经从小到大排序，查找返回arr中大于等于a的首个元素下标
    // a > arr[arr.length-1] 返回 -1
    // a < arr[0] 返回 0
    public static int binarySearch3(int[] arr, int a) {
        if (a > arr[arr.length-1]) return -1;
        if (a < arr[0]) return 0;
        int low = 0, high = arr.length-1, mid;
        while (low < high) {
            mid = low + (high-low)/2;
            if (a <= arr[mid]) {
                high = mid;
            } else {
                low = mid+1;
            }
        }
        return low;
    }
    // 测试 binarySearch3
    public static void test_binarySearch3() {
        int[] arr = Util.genArr(20);
        Arrays.sort(arr);
        Util.print("降序排序：", arr);
        int i = binarySearch3(arr, 10);
        System.out.println("查找首个>=10的元素：" + i);
        Util.sortR(arr);
        Util.print("升序排序：", arr);
        int i2 = binarySearch4(arr, 10);
        System.out.println("查找首个<=10的元素：" + i2);
    }

    // arr已经降序排序，查找返回arr中小于等于a的首个元素下标
    // a < arr[arr.length-1] 返回 -1
    // a > arr[0] 返回 0
    public static int binarySearch4(int[] arr, int a) {
        if (a < arr[arr.length-1]) return -1;
        if (a > arr[0]) return 0;
        int low = 0, high = arr.length-1, mid;
        while (low < high) {
            mid = low + (high-low)/2;
            if (a >= arr[mid]) {
                high = mid;
            } else {
                low = mid+1;
            }
        }
        return low;
    }
    // 测试 binarySearch4
    public static void test_binarySearch4() {
        int[] arr = Util.genArr(20);
        Util.sortR(arr);
        Util.print("降序排序：", arr);
        int i2 = binarySearch4(arr, 10);
        System.out.println("查找首个<=10的元素：" + i2);
    }
}
